10. Как видим, для все пар расстояние не меньше трёх, что соответствует условию задачи.

11. Ответ: 10110. Ещё пример задания

Р-14. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная

сумма длин всех шести кодовых слов? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Решение:

1. это задание удобнее решать с помощью дерева; условие Фано выполняется тогда, когда все выбранные кодовые слова заканчиваются в листьях дерева

2. построим дерево по известным кодовым словам: А – 0, Б – 10:

3. на оставшуюся свободную ветку нужно «повесить» 4 кодовых слова (для букв В, Г, Д, Е)

4. если выбрать один код длиной 3 (В – 110), то оставшиеся 3 кода нужно «повесить» на одну ветку, так, что на ней нужно делать две развилки:

5. суммарная длина кодовых слов будет в этом случае равна

1 + 2 + 3 + 4 + 2·5 = 20

6. попробуем другой вариант: оставшиеся 4 кода повесить на 4 ветки одинаковой длины:

7. суммарная длина кодовых слов будет в этом случае меньше, чем в предыдущем случае:

1 + 2 + 4·4 = 19

8. Ответ: 19. Ещё пример задания

Р-13. По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования:

а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование);

б) общая длина закодированного сообщения должна быть как можно меньше.

Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г?

1) А:0, Б:10, В:110, Г:111

2) А:0, Б:10, В:01, Г:11

3) А:1, Б:01, В:011, Г:001

4) А:00, Б:01, В:10, Г:11

Решение:

1. сначала выберем коды, в которых ни одно кодовое слово не совпадет с началом другого (такие коды называю префиксными)

2. для кода 2 условие «а» не выполняется, так как кодовое слово буквы В (01) начинается с кодового слова буквы А (0)

3. для кода 3 условие «а» не выполняется, так как кодовое слово буквы В (011) начинается с кодового слова буквы Б (01)

4. для кодов 1 и 4 условие выполняется, их рассматриваем дальше

5. считаем общее количество битов в сообщении для кода 1:

16∙1 + 8·2 + 4∙3 + 4∙3 = 56 битов

6. считаем общее количество битов в сообщении для кода 4:

16∙2 + 8·2 + 4∙2 + 4∙2 = 64 бита

7. код 1 даёт наименьшую длину сообщения, поэтому выбираем его

8. Ответ: 1. Ещё пример задания

Р-12. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0, для буквы Б – кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?

1) 7 2) 8 3) 9 4) 10

Решение (способ 1, исключение вариантов):